package mylist;

/**
 * Created with IntelliJ IDEA.
 * Description:
 */
public class Mylink {
    private ListNode head;
    class ListNode{
        public int value ;
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }
    public void creatList(){
        ListNode node1 =new ListNode(1);
        ListNode node2 =new ListNode(2);
        ListNode node3 =new ListNode(3);
        ListNode node4 =new ListNode(4);
        ListNode node5 =new ListNode(5);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        this.head=node1;
    }
    //得到单链表的长度
    public int size(){
        ListNode cur =head;
        int count=0;
        while (cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }
    //遍历
    public void display() {
        ListNode cur =head;
        while (cur!=null){
            System.out.print(cur.value+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //遍历
    public void display(ListNode nu) {
        ListNode cur =nu;
        while (cur!=null){
            System.out.print(cur.value+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur =head;
        while (cur!=null){
            if (cur.value==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        ListNode newnode =new ListNode(data);
        newnode.next=head;
        head=newnode;
    }
    //尾插法
    public void addLast(int data){
        ListNode cur =head;
        ListNode newnode=new ListNode(data);
        if (head==null){
            head=newnode;
            return;
        }
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=newnode;
    }
    public void checkPos(int index)throws PostExpect{
        if (index<0||index>size()){
            throw new PostExpect("下标异常");
        }

    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
       try {
           checkPos(index);
           ListNode cur =head;
           ListNode newnode =new ListNode(data);
           if (index==0){
               addFirst(data);
           }
           if (index==size()){
               addLast(data);
           }else {
               for (int i = index-1; i > 0; i--) {
                   cur=cur.next;
               }
               newnode.next=cur.next;
               cur.next=newnode;
           }
       }catch (PostExpect e){
           e.printStackTrace();
       }
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (head==null){
            return;
        }
        ListNode cur =head;
        if (cur.value==key){
            head =cur.next;
            return;
        }
        while (cur.next!=null){
            if (cur.next.value==key){
                ListNode del =cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
    }
    //错误
    public void removeAllkey2(int key){
        if (head==null){
            return;
        }
        while (head.value==key){
            head=head.next;
            if (head==null){
                return;
            }
        }
        ListNode cur =head;
        while (cur.next!=null){
            if (cur.next.value==key){
                ListNode del =cur.next;
                cur.next=del.next;
                if (cur.next==null){
                    return;
                }
            }
//            if (cur.next.next==null){
//                if (head.value==key){
//                    head =head.next;
//                }
//                return;
//            }
            cur=cur.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head==null){
            return;
        }
        ListNode cur =head.next;
        ListNode pre =head;
        while (cur!=null){
            if (cur.value==key){
                pre.next=cur.next;
                cur=cur.next;
            }else {
                cur=cur.next;
                pre=pre.next;
            }
        }
        if (head.value==key){
            head=head.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey3(int key){
        if (head==null){
            return;
        }
        while (head.value==key){
            head=head.next;
            if (head==null){
                return;
            }
        }
        ListNode cur =head.next;
        ListNode pre =head;
        while (cur!=null){
            if (cur.value==key){
                pre.next=cur.next;
                cur=cur.next;
            }else {
                cur=cur.next;
                pre=pre.next;
            }
        }
    }

   //清空链表
    public void clear() {
        head=null;
    }
    public ListNode reverseList() {
        if(head==null){
            return null;
        }
        ListNode cur =head.next;
        head.next =null;
        while(cur!=null){
            ListNode curt =cur.next;
            cur.next=head;
            head=cur;
            cur=curt;
        }
        return head;
    }
    public ListNode middleNode() {
        if(head==null){
            return null;
        }
        ListNode cur =head;
        int count =0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        count=count/2;
        while(count>0){
            count--;
            head=head.next;
        }
        return head;
    }
    public ListNode middleNode2() {
        if(head==null){
            return null;
        }
        ListNode cur =head;
        ListNode slow =head;
        ListNode fast =head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //k值有效
    //方法1：
    public int kthToLast(int k) {
        if(head==null){
            return -1;
        }
        ListNode cur =head;
        int count =0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        int num =count-k;
        while(num>0){
            num--;
            head=head.next;
        }
        return head.value;
    }
    //方法2：
    public int kthToLast1( int k) {
        if(head==null){
            return -1;
        }
        ListNode fast =head;
        ListNode slow =head;
        while(k-->0){
            fast =fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.value;
    }
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if(headA==null&&headB==null){
            return null;
        }
        ListNode head =new ListNode(1);
        ListNode cur =head;
        while(headA!=null&&headB!=null){
            if(headA.value>headB.value){
                cur.next=headB;
                headB=headB.next;
                cur=cur.next;
            }else{
                cur.next=headA;
                headA=headA.next;
                cur=cur.next;
            }
        }
        if(headA==null){
            cur.next=headB;
        }
        if(headB==null){
            cur.next=headA;
        }
        return head.next;
    }
    public ListNode partition(int x) {
        if(head==null){
            return null;
        }
        ListNode cur =head;
        ListNode as =null;
        ListNode bs =null;
        ListNode be =null;
        ListNode ae =null;
        while(cur!=null){
            if(cur.value<x){
                if(as==null){
                    as=ae=cur;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }else{
                if(bs==null){
                    bs=be=cur;
                }else{
                    be.next=cur;
                    be=be.next;
                }

            }
            cur=cur.next;
        }
        if(as==null){
            return bs;
        }
        ae.next=bs;
        if(bs!=null){
            be.next=null;
        }
        return as;
    }
    public boolean chkPalindrome() {
        ListNode cur =head;
        ListNode slow =head;
        ListNode fast =head;
        ListNode last =head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        last=slow.next;
        while(last!=null){
            ListNode tmp =last.next;
            last.next=slow;
            slow=last;
            last=tmp;
        }
        while(head!=slow){
            if(head.value==slow.value){
                if(head.next==slow){
                    return true;
                }
            }else{
                return false;
            }
            slow=slow.next;
            head=head.next;
        }
        return true;
    }
    public boolean hasCycle() {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }

        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode listA, ListNode listB) {
        if(listA==null||listB==null){
            return null;
        }
        ListNode as =listA;
        ListNode bs =listB;
        int numA=0;
        int numB=0;
        while(as!=null){
            as=as.next;
            numA++;
        }
        while(bs!=null){
            bs=bs.next;
            numB++;
        }
        if(numA>numB){
            int k=numA-numB;
            while(k>0){
                listA=listA.next;
                k--;
            }
        }else{
            int k=numB-numA;
            while(k>0){
                listB=listB.next;
                k--;
            }
        }

        while(listA!=listB){
            listA=listA.next;
            listB=listB.next;
        }
        if(listA==null){
            return null;
        }
        return listA;
    }
    public ListNode detectCycle() {
        if(head==null){
            return null;
        }
        ListNode fast =head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }

        }
        if(fast==null||fast.next==null){
            return null;
        }
        while(fast!=head){
            head=head.next;
            fast=fast.next;
        }
        return head;
    }
}
